package gold.gold02;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * 先遍历一遍变成链表, 再遍历一遍列表吧。
 * 34, 注意只要是用iter迭代, 就需要对边界进行判断。时间都差不多。
 */
public class S0406后继者 {
    // 题意为返回p节点中序遍历的后一个节点
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null) return null;
        List<TreeNode> resultList = new LinkedList<>();
        makeList(root, resultList);
        // 使用iter迭代 List
        Iterator<TreeNode> iter = resultList.iterator();
        while (iter.hasNext()){
            TreeNode temp1 = iter.next();
            if(temp1.val == p.val){
                if(iter.hasNext()) return iter.next();
                return null;
            }
        }
        return null;
    }
    // 中序遍历标准流程 node->list
    private void makeList(TreeNode node, List<TreeNode> list){
        if(node.left != null)
            makeList(node.left, list);
        list.add(node);
        if(node.right != null)
            makeList(node.right, list);
    }

    public TreeNode inorderSuccessor2(TreeNode root, TreeNode p) {
        //问题的本质是找到最靠近p节点且值大于p节点值的那个节点
        TreeNode res = root;
        //设定临时变量方便对树的操作
        TreeNode temp = root;
        while (temp != null){
            //如果当前节点的值小于等于目标节点的值，那一定不是答案节点，且答案节点在该节点的右孩子中
            if (temp.val <= p.val) {
                temp = temp.right;
            } else {
                //如果当前节点的值大于目标节点的值，那么该节点有可能是答案节点，具体是不是需要遍历其左孩子，寻找更靠近p节点值的答案
                res = temp;
                temp = temp.left;
            }
        }
        return res.val <= p.val ? null : res;
    }


}
